package com.aqie.easy.sort;

import java.util.LinkedList;

/**
 *
 * 1030  距离顺序排列矩阵单元格
 * todo
 *
 */
public class AllCellsDistOrder {
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        int[][] ans = new int[R * C][2];
        int i = 0;
        boolean[][] visited = new boolean[R][C];
        LinkedList<int[]> deque = new LinkedList<>();
        deque.offer(new int[]{r0, c0});
        while (!deque.isEmpty()) {
            int[] poll = deque.poll();
            int r = poll[0];
            int c = poll[1];
            if (r < 0 || r >= R || c < 0 || c >= C || visited[r][c]) {
                continue;
            }

            ans[i++] = poll;
            visited[r][c] = true;

            deque.offer(new int[]{r + 1, c});
            deque.offer(new int[]{r - 1, c});
            deque.offer(new int[]{r, c + 1});
            deque.offer(new int[]{r, c - 1});
        }
        return ans;
    }
}
